<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>剑指Offer-二叉树 | ShenShilei's Blog</title><meta name="keywords" content="算法"><meta name="author" content="Shen Shilei"><meta name="copyright" content="Shen Shilei"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><meta name="description" content="剑指Offer刷题。">
<meta property="og:type" content="article">
<meta property="og:title" content="剑指Offer-二叉树">
<meta property="og:url" content="https://blog.shenshilei.site/post/e1b0/index.html">
<meta property="og:site_name" content="ShenShilei&#39;s Blog">
<meta property="og:description" content="剑指Offer刷题。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/317.jpg">
<meta property="article:published_time" content="2020-08-07T13:03:04.000Z">
<meta property="article:modified_time" content="2020-08-13T02:50:38.000Z">
<meta property="article:author" content="Shen Shilei">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/317.jpg"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://blog.shenshilei.site/post/e1b0/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.css"><script>var GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: {"path":"search.xml","languages":{"hits_empty":"找不到您查询的内容：${query}"}},
  translate: undefined,
  noticeOutdate: {"limitDay":180,"position":"top","messagePrev":"这是一篇创建于","messageNext":"天前的文章，其中的信息可能已经有所发展或是发生改变。"},
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: {"limitCount":50,"languages":{"author":"作者: Shen Shilei","link":"链接: ","source":"来源: ShenShilei's Blog","info":"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},
  ClickShowText: undefined,
  lightbox: 'fancybox',
  Snackbar: {"chs_to_cht":"你已切换为繁体","cht_to_chs":"你已切换为简体","day_to_night":"你已切换为深色模式","night_to_day":"你已切换为浅色模式","bgLight":"#49b1f5","bgDark":"#121212","position":"top-center"},
  justifiedGallery: {
    js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
    css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isanchor: false
};

var saveToLocal = {
  set: function setWithExpiry(key, value, ttl) {
    const now = new Date()
    const expiryDay = ttl * 86400000
    const item = {
      value: value,
      expiry: now.getTime() + expiryDay,
    }
    localStorage.setItem(key, JSON.stringify(item))
  },

  get: function getWithExpiry(key) {
    const itemStr = localStorage.getItem(key)

    if (!itemStr) {
      return undefined
    }
    const item = JSON.parse(itemStr)
    const now = new Date()

    if (now.getTime() > item.expiry) {
      localStorage.removeItem(key)
      return undefined
    }
    return item.value
  }
}</script><script id="config_change">var GLOBAL_CONFIG_SITE = { 
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2020-08-13 10:50:38'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(function () {  window.activateDarkMode = function () {
    document.documentElement.setAttribute('data-theme', 'dark')
    if (document.querySelector('meta[name="theme-color"]') !== null) {
      document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
    }
  }
  window.activateLightMode = function () {
    document.documentElement.setAttribute('data-theme', 'light')
   if (document.querySelector('meta[name="theme-color"]') !== null) {
      document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
    }
  }
  const autoChangeMode = '1'
  const t = saveToLocal.get('theme')
  if (autoChangeMode === '1') {
    const isDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches
    const isLightMode = window.matchMedia('(prefers-color-scheme: light)').matches
    const isNotSpecified = window.matchMedia('(prefers-color-scheme: no-preference)').matches
    const hasNoSupport = !isDarkMode && !isLightMode && !isNotSpecified
    if (t === undefined) {
      if (isLightMode) activateLightMode()
      else if (isDarkMode) activateDarkMode()
      else if (isNotSpecified || hasNoSupport) {
        const now = new Date()
        const hour = now.getHours()
        const isNight = hour <= 6 || hour >= 18
        isNight ? activateDarkMode() : activateLightMode()
      }
      window.matchMedia('(prefers-color-scheme: dark)').addListener(function (e) {
        if (saveToLocal.get('theme') === undefined) {
          e.matches ? activateDarkMode() : activateLightMode()
        }
      })
    } else if (t === 'light') activateLightMode()
    else activateDarkMode()
  } else if (autoChangeMode === '2') {
    const now = new Date()
    const hour = now.getHours()
    const isNight = hour <= 6 || hour >= 18
    if (t === undefined) isNight ? activateDarkMode() : activateLightMode()
    else if (t === 'light') activateLightMode()
    else activateDarkMode()
  } else {
    if (t === 'dark') activateDarkMode()
    else if (t === 'light') activateLightMode()
  }})()</script><link rel="stylesheet" href="https://fonts.googleapis.com/css?family=Noto+Serif+SC"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/kang-static/Hexo/css/iconfont.min.css"><style type="text/css">.aplayer.aplayer-narrow .aplayer-body{left: -66px !important;transition: left 1s;} .aplayer.aplayer-narrow .aplayer-body:hover{left: 0 !important;}</style><style type="text/css">body{cursor: url(https://cdn.jsdelivr.net/gh/Justlovesmile/CDN/image/cursor.ico),default}</style><meta name="generator" content="Hexo 5.4.0"></head><body><div id="web_bg"></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="author-avatar"><img class="avatar-img" src="https://cdn.jsdelivr.net/gh/shenshilei1022/cdn@1.6/img/custom/avatar.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">92</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">60</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">38</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/artitalk/"><i class="fa-fw fa fa-comment"></i><span> 说说</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 文章</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></li><li><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></li><li><a class="site-page" href="/analytics/"><i class="fa-fw fas fa-chart-line"></i><span> 统计</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/bangumis/"><i class="fa-fw fab fa-youtube"></i><span> 番剧</span></a></li><li><a class="site-page" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li><li><a class="site-page" href="/books/"><i class="fa-fw fas fa-book"></i><span> 书单</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 工具箱</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/box/"><i class="fa-fw fas fa-th-large"></i><span> 网站聚合</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://cdn.jsdelivr.net/gh/shenshilei1022/cdn@2.0/"><i class="fa-fw fa fa-hdd"></i><span> MyCDN</span></a></li><li><a class="site-page" href="/note/"><i class="fa-fw fas fa-business-time"></i><span> 便利贴</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://music.shenshilei.site/"><i class="fa-fw fas fa-music"></i><span> 音乐播放器</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://webssh.shenshilei.site/"><i class="fa-fw fas fa-terminal"></i><span> SSH在线连接</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/comment/"><i class="fa-fw fa fa-pencil-alt"></i><span> 留言板</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-paperclip"></i><span> 关于</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/about/"><i class="fa-fw fas fa-rocket"></i><span> 我</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://shenshilei1022.avosapps.us/"><i class="fa-fw fas fa-list-alt"></i><span> 评论管理</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="http://bt.shenshilei.site:8888/shenshilei"><i class="fa-fw fas fa-window-maximize"></i><span> 服务器管理</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://console.leancloud.app/applist.html#/apps"><i class="fa-fw fas fa-window-restore"></i><span> leancloud应用</span></a></li></ul></div></div></div></div><div id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url(https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/317.jpg)"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">ShenShilei's Blog</a></span><span id="menus"><div id="search_button"><a class="site-page social-icon search"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/artitalk/"><i class="fa-fw fa fa-comment"></i><span> 说说</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 文章</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></li><li><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></li><li><a class="site-page" href="/categories/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></li><li><a class="site-page" href="/analytics/"><i class="fa-fw fas fa-chart-line"></i><span> 统计</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/bangumis/"><i class="fa-fw fab fa-youtube"></i><span> 番剧</span></a></li><li><a class="site-page" href="/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li><li><a class="site-page" href="/books/"><i class="fa-fw fas fa-book"></i><span> 书单</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 工具箱</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/box/"><i class="fa-fw fas fa-th-large"></i><span> 网站聚合</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://cdn.jsdelivr.net/gh/shenshilei1022/cdn@2.0/"><i class="fa-fw fa fa-hdd"></i><span> MyCDN</span></a></li><li><a class="site-page" href="/note/"><i class="fa-fw fas fa-business-time"></i><span> 便利贴</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://music.shenshilei.site/"><i class="fa-fw fas fa-music"></i><span> 音乐播放器</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://webssh.shenshilei.site/"><i class="fa-fw fas fa-terminal"></i><span> SSH在线连接</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/comment/"><i class="fa-fw fa fa-pencil-alt"></i><span> 留言板</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><i class="fa-fw fas fa-paperclip"></i><span> 关于</span><i class="fas fa-chevron-down expand"></i></a><ul class="menus_item_child"><li><a class="site-page" href="/about/"><i class="fa-fw fas fa-rocket"></i><span> 我</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://shenshilei1022.avosapps.us/"><i class="fa-fw fas fa-list-alt"></i><span> 评论管理</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="http://bt.shenshilei.site:8888/shenshilei"><i class="fa-fw fas fa-window-maximize"></i><span> 服务器管理</span></a></li><li><a class="site-page" target="_blank" rel="noopener" href="https://console.leancloud.app/applist.html#/apps"><i class="fa-fw fas fa-window-restore"></i><span> leancloud应用</span></a></li></ul></div></div><span class="close" id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></span></span></nav><div id="post-info"><h1 class="post-title">剑指Offer-二叉树</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2020-08-07T13:03:04.000Z" title="发表于 2020-08-07 21:03:04">2020-08-07</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2020-08-13T02:50:38.000Z" title="更新于 2020-08-13 10:50:38">2020-08-13</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a><i class="fas fa-angle-right post-meta-separator"></i><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E7%AE%97%E6%B3%95/%E5%89%91%E6%8C%87Offer/">剑指Offer</a></span></div><div class="meta-secondline"> <span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">4.3k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>16分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span><span class="post-meta-separator">|</span><span class="post-meta-commentcount"><i class="far fa-comments fa-fw post-meta-icon"></i><span class="post-meta-label">评论数:</span><a href="/post/e1b0/#post-comment" itemprop="discussionUrl"><span class="valine-comment-count comment-count" data-xid="/post/e1b0/" itemprop="commentCount"></span></a></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><p>之前一直对树这种数据结构比较畏惧，感觉很难，就没啃这块骨头🤔。这两天就来啃它！实际上它确实难，但是没有我想象中的那么难😂</p>
<h2 id="1-为什么要使用树？"><a href="#1-为什么要使用树？" class="headerlink" title="1. 为什么要使用树？"></a>1. 为什么要使用树？</h2><p>对于有序数组，我们知道它查找非常快（二分查找）。但是想要在数组中插入一个数据，我们就需要先找到插入数据的位置，将所有插入位置后的数据都向后移一位，才能完成一个数据的插入。平均需要$n/2$次。很费时，删除数据也是一样的道理。</p>
<p>对于链表，正好和数组相反，它插入和删除数据非常快速，我们只需要修改引用即可，但查找数据只能从链表的头部或尾部开始一个一个查找，这样查找平均也需要$n/2$次。</p>
<p>所以希望有一种数据结构能够同时具有查找快和插入删除快的优点，于是便有了树👍。</p>
<h2 id="2-树"><a href="#2-树" class="headerlink" title="2. 树"></a>2. 树</h2><p>树是一种抽象数据结构（Abstract Data Type, ADT），用来模拟具有树状结构性质的数据集合。它是由n(n &gt; 0)个<strong>节点</strong>通过连接它们的<strong>边</strong>组成的具有层次关系的集合。叫它“树”的原因是这样的结构看起来很像一棵倒挂的树，即它是根在上，叶在下的。</p>
<p><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/326.jpg" alt=""></p>
<ul>
<li>节点：图中的黄色圆圈都表示节点。这棵树中共有8个节点。在Java中，节点一般代表对象。</li>
<li>边：连接节点的线称为边。在Java中，边一般是引用。</li>
</ul>
<p>树有很多种，像上图就称为多路树（节点的子节点数大于两个）。这里主要先学习二叉树[节点的子节点数小于等于两个]。</p>
<h2 id="3-树的常用名词"><a href="#3-树的常用名词" class="headerlink" title="3. 树的常用名词"></a>3. 树的常用名词</h2><p><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/327.jpg" alt=""></p>
<ul>
<li>根：树顶端的节点。一棵树只有一个根，从根到其它节点的路径有且只能有一条，否则不能称之为树。</li>
<li>父节点：若一个节点含有子节点，那么称这个节点是子节点的父节点。例如B是D的父节点。</li>
<li>子节点：和父节点是相对的概念，若一个节点有父节点，那么称这个节点是父节点的子节点。例如D是B的子节点。</li>
<li>兄弟节点：具有相同父节点的节点称为兄弟节点。例如D和E是兄弟节点。</li>
<li>叶节点：没有子节点的节点称为叶节点。例如D, E, F, G</li>
<li>子树：每个节点都可以作为子树的根，例如在这棵树中，节点B, D, E组成子树，B是子树的根。</li>
<li>节点的层次：从根开始定义，根为第一层，根的子节点为第二层，依次类推。</li>
<li>深度：对于任意节点n，n的深度是从根到n的唯一路径长。根的深度为0。例如D的深度为2，B的深度为1。</li>
<li>高度：对于任意节点n，n的高度是从n到一个叶节点的最长路径长。叶节点的高度为0。例如B的高度为1，A的高度为2。</li>
</ul>
<h2 id="4-二叉树"><a href="#4-二叉树" class="headerlink" title="4. 二叉树"></a>4. 二叉树</h2><p>二叉树的每个节点最多只能有两个子节点。</p>
<p>如果给二叉树加一个条件，可以得到一种<strong>二叉搜索树(binary search tree)</strong> 的特殊二叉树。</p>
<p>它的条件是这样的：对于它的一个节点，如果节点的左子树不为空，那么它左子树的值都小于该节点；如果节点的右子树不为空，那么它右子树的值都大于该节点。</p>
<p><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/328.jpg" alt=""></p>
<h2 id="5-树的遍历"><a href="#5-树的遍历" class="headerlink" title="5. 树的遍历"></a>5. 树的遍历</h2><ul>
<li>前序遍历：根节点 -&gt; 左子节点 -&gt; 右子节点</li>
<li>中序遍历：左子节点 -&gt; 根节点 -&gt; 右子节点</li>
<li>后序遍历：左子节点 -&gt; 右子节点 -&gt; 根节点</li>
</ul>
<p><em>可以根据箭头方向来记忆</em><br><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/329.jpg" alt=""></p>
<p>例如上图的二叉搜索树，经过遍历后的结果如下：</p>
<blockquote>
<p>前序遍历：5 3 1 4 8 6 10<br>中序遍历：1 3 4 5 6 8 10<br>后序遍历：1 4 3 6 10 8 5</p>
</blockquote>
<p>我们可以发现几个规律：</p>
<ol>
<li>前序遍历得到的序列的第一个元素是树的根节点。</li>
<li>后续遍历得到的序列的最后一个元素是树的根节点。</li>
<li>对于二叉搜索树，经过中序遍历得到的序列是一个<strong>有序数列！（很重要）</strong></li>
</ol>
<h2 id="6-几个关于树的题目"><a href="#6-几个关于树的题目" class="headerlink" title="6. 几个关于树的题目"></a>6. 几个关于树的题目</h2><h3 id="6-1-二叉树的深度"><a href="#6-1-二叉树的深度" class="headerlink" title="6.1 二叉树的深度"></a>6.1 二叉树的深度</h3><blockquote>
<p>题目描述：输入一棵二叉树，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。</p>
</blockquote>
<p>这里因为包括根和叶节点，这里要求的树的深度相当于树的层数。</p>
<p>解法：</p>
<ol>
<li><strong>递归法</strong></li>
</ol>
<p>思路：对于一个节点，判断其左右子树的高度，最终返回高度较大的值加1.（终止条件：当节点为null时，返回0）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">TreeDepth</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> l = TreeDepth(root.left);</span><br><span class="line">        <span class="keyword">int</span> r = TreeDepth(root.right);</span><br><span class="line">        <span class="keyword">return</span> (l &gt; r ? l : r) + <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<div class="note info no-icon flat"><p>时间复杂度为$O(n)$，空间复杂度为$O(n)$</p>
</div>
<ol>
<li><strong>层次遍历</strong></li>
</ol>
<p>思路：使用队列作为辅助空间。</p>
<ul>
<li>让节点进入队列。此时记录下队列的长度，这个大小就是树当前层的总节点个数。</li>
<li>遍历这个大小，让节点出队，将节点的左右子节点入队。</li>
<li>循环结束，表示当前层遍历完毕，深度加一。</li>
<li>重复前面这个过程直到队列为空停止。<br><strong>这是一个模板算法，牢记！</strong></li>
</ul>
<p><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/330.jpg" alt=""></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">import</span> java.util.LinkedList;</span><br><span class="line"><span class="keyword">import</span> java.util.Queue;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">TreeDepth</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        queue.offer(root);</span><br><span class="line">        <span class="keyword">int</span> depth = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">int</span> count;</span><br><span class="line">        TreeNode node;</span><br><span class="line">        <span class="keyword">while</span> (queue.size() != <span class="number">0</span>) &#123;</span><br><span class="line">            <span class="comment">// 当前层总节点个数</span></span><br><span class="line">            count = queue.size();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; count; i++) &#123;</span><br><span class="line">                <span class="comment">// 队列中节点出队</span></span><br><span class="line">                node = queue.poll();</span><br><span class="line">                <span class="comment">// 将节点的左右子节点入队</span></span><br><span class="line">                <span class="keyword">if</span> (node.left != <span class="keyword">null</span>) queue.offer(node.left);</span><br><span class="line">                <span class="keyword">if</span> (node.right != <span class="keyword">null</span>) queue.offer(node.right);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 一个循环结束，说明遍历完一层</span></span><br><span class="line">            depth++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> depth;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<div class="note info no-icon flat"><p>时间复杂度为$O(n)$，二叉树每个节点遍历一次。<br>空间复杂度为$O(n)$，（最差）。树平衡时，队列最多存储$n/2$个节点。</p>
</div>
<h3 id="6-2-二叉树的镜像"><a href="#6-2-二叉树的镜像" class="headerlink" title="6.2 二叉树的镜像"></a>6.2 二叉树的镜像</h3><blockquote>
<p>题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。</p>
</blockquote>
<div class="note primary no-icon flat"><p>二叉树的镜像定义：<br><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line">   源二叉树</span><br><span class="line">    8</span><br><span class="line">   /  \</span><br><span class="line">  6   10</span><br><span class="line"> / \  / \</span><br><span class="line">5  7 9 11</span><br><span class="line">镜像二叉树</span><br><span class="line">    8</span><br><span class="line">   /  \</span><br><span class="line">  10   6</span><br><span class="line"> / \  / \</span><br><span class="line">11 9 7  5</span><br></pre></td></tr></table></figure></p>
</div>
<p>解法：</p>
<ol>
<li><strong>递归法</strong></li>
</ol>
<p>思路：对当前节点的左右节点进行互换。接着对当前节点的左节点和右节点进行递归。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">Mirror</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span> ;</span><br><span class="line">        TreeNode temp = root.left;</span><br><span class="line">        root.left = root.right;</span><br><span class="line">        root.right = temp;</span><br><span class="line">        Mirror(root.left);</span><br><span class="line">        Mirror(root.right);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<div class="note info no-icon flat"><p>时间复杂度为$O(n)$，二叉树每个节点遍历一次。<br>空间复杂度为$O(n)$，每个节点都会在递归栈中存一次。</p>
</div>
<ol>
<li><strong>层次遍历</strong></li>
</ol>
<p>思路：使用上面学到的层次遍历，对每个节点的左右节点进行左右互换。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">import</span> java.util.LinkedList;</span><br><span class="line"><span class="keyword">import</span> java.util.Queue;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">Mirror</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span>;</span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        queue.offer(root);</span><br><span class="line">        <span class="keyword">int</span> count;</span><br><span class="line">        TreeNode cur;</span><br><span class="line">        TreeNode temp;</span><br><span class="line">        <span class="keyword">while</span> (queue.size() != <span class="number">0</span>) &#123;</span><br><span class="line">            count = queue.size();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; count; i++) &#123;</span><br><span class="line">                cur = queue.poll();</span><br><span class="line">                <span class="keyword">if</span> (cur.left != <span class="keyword">null</span>) queue.offer(cur.left);</span><br><span class="line">                <span class="keyword">if</span> (cur.right != <span class="keyword">null</span>) queue.offer(cur.right);</span><br><span class="line">                <span class="comment">// 交换节点</span></span><br><span class="line">                temp = cur.left;</span><br><span class="line">                cur.left = cur.right;</span><br><span class="line">                cur.right = temp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<div class="note info no-icon flat"><p>时间复杂度为$O(n)$，二叉树每个节点遍历一次。<br>空间复杂度为$O(n)$，（最差）。树平衡时，队列最多存储$n/2$个节点。</p>
</div>
<h3 id="6-3-重建二叉树"><a href="#6-3-重建二叉树" class="headerlink" title="6.3 重建二叉树"></a>6.3 重建二叉树</h3><blockquote>
<p>题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。</p>
</blockquote>
<p>思路：由于前序遍历的第一个元素即是树的根节点，再通过根节点在中序遍历中划分数组（根节点左边的元素即为左树元素，右边的元素即为右树元素。），重复这个过程，直到遍历完中序遍历序列。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * Definition for binary tree</span></span><br><span class="line"><span class="comment"> * public class TreeNode &#123;</span></span><br><span class="line"><span class="comment"> *     int val;</span></span><br><span class="line"><span class="comment"> *     TreeNode left;</span></span><br><span class="line"><span class="comment"> *     TreeNode right;</span></span><br><span class="line"><span class="comment"> *     TreeNode(int x) &#123; val = x; &#125;</span></span><br><span class="line"><span class="comment"> * &#125;</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">import</span> java.util.Arrays;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> TreeNode <span class="title">reConstructBinaryTree</span><span class="params">(<span class="keyword">int</span> [] pre,<span class="keyword">int</span> [] in)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (pre == <span class="keyword">null</span> || in == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">if</span> (pre.length == <span class="number">0</span> || in.length == <span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        <span class="comment">// 创建根节点</span></span><br><span class="line">        TreeNode root = <span class="keyword">new</span> TreeNode(pre[<span class="number">0</span>]);</span><br><span class="line">        <span class="comment">// 根据根节点划分中序遍历序列，为根节点添加左右子树</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; in.length; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (root.val == in[i]) &#123;</span><br><span class="line">                <span class="comment">// 左子树</span></span><br><span class="line">                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, <span class="number">1</span>, i + <span class="number">1</span>), Arrays.copyOfRange(in, <span class="number">0</span>, i));</span><br><span class="line">                <span class="comment">// 右子树</span></span><br><span class="line">                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + <span class="number">1</span>, pre.length), Arrays.copyOfRange(in, i + <span class="number">1</span>, in.length));</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>同理，根据后序遍历和中序遍历，也能重建一个二叉树。（后序遍历的最后一个元素是根节点。🔑）</p>
<h3 id="6-4-序列化二叉树"><a href="#6-4-序列化二叉树" class="headerlink" title="6.4 序列化二叉树"></a>6.4 序列化二叉树</h3><blockquote>
<p>题目描述：请实现两个函数，分别用来序列化和反序列化二叉树<br>二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。<br>二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。<br>例如，我们可以把一个只有根节点为1的二叉树序列化为”1,”，然后通过自己的函数来解析回这个二叉树</p>
</blockquote>
<p>思路：对于序列化，可以将树遍历一遍，将对应的节点转换为字符串即可；对于反序列化，将每一个节点添加到队列中，为其添加左右子节点，直到队列为空。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">import</span> java.util.LinkedList;</span><br><span class="line"><span class="keyword">import</span> java.util.Queue;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function">String <span class="title">Serialize</span><span class="params">(TreeNode root)</span> </span>&#123;</span><br><span class="line">        StringBuilder result = <span class="keyword">new</span> StringBuilder(<span class="string">&quot;&quot;</span>);</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span> result.toString();</span><br><span class="line">        <span class="comment">// 层序遍历</span></span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        queue.offer(root);</span><br><span class="line">        <span class="comment">// 添加父节点</span></span><br><span class="line">        result.append(String.valueOf(root.val) + <span class="string">&quot;!&quot;</span>);</span><br><span class="line">        TreeNode temp;</span><br><span class="line">        <span class="keyword">while</span> (!queue.isEmpty()) &#123;</span><br><span class="line">            <span class="comment">// 只添加子节点</span></span><br><span class="line">            temp = queue.poll();</span><br><span class="line">            <span class="keyword">if</span> (temp.left != <span class="keyword">null</span>) &#123;</span><br><span class="line">                result.append(String.valueOf(temp.left.val) + <span class="string">&quot;!&quot;</span>);</span><br><span class="line">                queue.offer(temp.left);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                result.append(<span class="string">&quot;#!&quot;</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (temp.right != <span class="keyword">null</span>) &#123;</span><br><span class="line">                result.append(String.valueOf(temp.right.val) + <span class="string">&quot;!&quot;</span>);</span><br><span class="line">                queue.offer(temp.right);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                result.append(<span class="string">&quot;#!&quot;</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> result.toString();</span><br><span class="line">  &#125;</span><br><span class="line">    <span class="function">TreeNode <span class="title">Deserialize</span><span class="params">(String str)</span> </span>&#123;</span><br><span class="line">       <span class="comment">// 注意字符串比较</span></span><br><span class="line">        <span class="keyword">if</span> (str.equals(<span class="string">&quot;&quot;</span>)) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        String[] list = str.split(<span class="string">&quot;!&quot;</span>);</span><br><span class="line">        <span class="comment">// 先建立根节点</span></span><br><span class="line">        TreeNode root = <span class="keyword">new</span> TreeNode(Integer.parseInt(list[<span class="number">0</span>]));</span><br><span class="line">        <span class="comment">// 使用队列管理需要添加子节点的节点</span></span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        queue.offer(root);</span><br><span class="line">        TreeNode temp;</span><br><span class="line">        <span class="comment">// 使用index来遍历list，其中index元素的左右子节点分别为2*index+1, 2*index+2</span></span><br><span class="line">        <span class="keyword">int</span> index = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span> (!queue.isEmpty() &amp;&amp; index &lt; list.length) &#123;</span><br><span class="line">            temp = queue.poll();</span><br><span class="line">            <span class="comment">// 这里注意超界问题，index小于list.length, 但2*index+1不一定小于list.length</span></span><br><span class="line">            <span class="keyword">if</span> (<span class="number">2</span> * index + <span class="number">1</span> &lt; list.length &amp;&amp; !list[<span class="number">2</span> * index + <span class="number">1</span>].equals(<span class="string">&quot;#&quot;</span>)) &#123;</span><br><span class="line">                temp.left = <span class="keyword">new</span> TreeNode(Integer.parseInt(list[<span class="number">2</span> * index + <span class="number">1</span>]));</span><br><span class="line">                <span class="comment">// 添加到队列</span></span><br><span class="line">                queue.offer(temp.left);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                temp.left = <span class="keyword">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (<span class="number">2</span> * index + <span class="number">2</span> &lt; list.length &amp;&amp; !list[<span class="number">2</span> * index + <span class="number">2</span>].equals(<span class="string">&quot;#&quot;</span>)) &#123;</span><br><span class="line">                temp.right = <span class="keyword">new</span> TreeNode(Integer.parseInt(list[<span class="number">2</span> * index + <span class="number">2</span>]));</span><br><span class="line">                <span class="comment">// 添加到队列</span></span><br><span class="line">                queue.offer(temp.right);</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                temp.right = <span class="keyword">null</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">// 增加索引值</span></span><br><span class="line">            index++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> root;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="6-5-二叉搜索树的后序遍历序列"><a href="#6-5-二叉搜索树的后序遍历序列" class="headerlink" title="6.5 二叉搜索树的后序遍历序列"></a>6.5 二叉搜索树的后序遍历序列</h3><blockquote>
<p>题目描述：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes，否则输出No。假设输入的数组的任意两个数字都互不相同。</p>
</blockquote>
<p>思路：后序遍历的序列是树的根节点，然后遍历除去根节点的序列，找到第一个大于根节点值的索引，此时索引左边为左子树的元素（均小于根节点），而右边为右子树的元素（应大于根节点）[不满足这一条直接返回false]。最终左索引大于等于右索引返回true。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">VerifySquenceOfBST</span><span class="params">(<span class="keyword">int</span> [] sequence)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (sequence == <span class="keyword">null</span> || sequence.length == <span class="number">0</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="keyword">return</span> judgeOrder(sequence, <span class="number">0</span>, sequence.length - <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">judgeOrder</span><span class="params">(<span class="keyword">int</span>[] sequence, <span class="keyword">int</span> start, <span class="keyword">int</span> end)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 结束条件</span></span><br><span class="line">        <span class="keyword">if</span> (start &gt;= end) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="comment">// 根节点</span></span><br><span class="line">        <span class="keyword">int</span> root = sequence[end];</span><br><span class="line">        <span class="comment">// 分割节点索引</span></span><br><span class="line">        <span class="keyword">int</span> split = start;</span><br><span class="line">        <span class="keyword">while</span> (split &lt; end &amp;&amp; sequence[split] &lt; root) split++;</span><br><span class="line">        <span class="comment">// 判断右子树中是否有不满足条件的情况</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = split; i &lt; end; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (sequence[i] &lt; root) &#123;</span><br><span class="line">                <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// 注意end - 1，将当前的根节点剔除</span></span><br><span class="line">        <span class="keyword">return</span> judgeOrder(sequence, start, split - <span class="number">1</span>) &amp;&amp; judgeOrder(sequence, split, end - <span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="6-6-树的子结构"><a href="#6-6-树的子结构" class="headerlink" title="6.6 树的子结构"></a>6.6 树的子结构</h3><blockquote>
<p>题目描述：输入两颗二叉树A, B，判断B是不是A的子结构。（ps: 我们约定空树不是任意一个树的子结构）</p>
</blockquote>
<p>思路：首先我们应该遍历大树（A树），找到节点和小树（B树）的根节点相同，然后递归判断节点下的左右子节点是否相同。直到子树遍历完，说明B是A的子结构；否则不是。</p>
<p><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/331.jpg" alt=""></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">import</span> java.util.LinkedList;</span><br><span class="line"><span class="keyword">import</span> java.util.Queue;</span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">HasSubtree</span><span class="params">(TreeNode root1,TreeNode root2)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (root2 == <span class="keyword">null</span> || root1 == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">        queue.offer(root1);</span><br><span class="line">        TreeNode temp;</span><br><span class="line">        <span class="keyword">while</span> (!queue.isEmpty()) &#123;</span><br><span class="line">            temp = queue.poll();</span><br><span class="line">            <span class="keyword">if</span> (temp.val == root2.val) &#123;</span><br><span class="line">                <span class="keyword">if</span> (judge(temp, root2)) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span> (temp.left != <span class="keyword">null</span>) queue.offer(temp.left);</span><br><span class="line">            <span class="keyword">if</span> (temp.right != <span class="keyword">null</span>) queue.offer(temp.right);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">private</span> <span class="keyword">boolean</span> <span class="title">judge</span><span class="params">(TreeNode root1, TreeNode root2)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 如果小树递归到空，则一定为大树的子结构</span></span><br><span class="line">        <span class="keyword">if</span> (root2 == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="comment">// 如果小树不为空而大树为空，则小树不为大树的子结构</span></span><br><span class="line">        <span class="keyword">if</span> (root1 == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="keyword">if</span> (root1.val == root2.val) &#123;</span><br><span class="line">            <span class="keyword">return</span> judge(root1.left, root2.left) &amp;&amp; judge(root1.right, root2.right);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="6-7-二叉树中和为某一值的路径"><a href="#6-7-二叉树中和为某一值的路径" class="headerlink" title="6.7 二叉树中和为某一值的路径"></a>6.7 二叉树中和为某一值的路径</h3><blockquote>
<p>题目描述：输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中节点值的和为输入整数的所有路径。路径定义为从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。</p>
</blockquote>
<p>思路：首先添加节点到路径中，target减去节点的值，判断target是否等于0且节点是否为叶节点，满足则将路径添加到结果中，否则继续递归左右子节点。递归完成后要将路径的最后一个节点删除（即向后走一步，给兄弟节点腾位置。）</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.ArrayList;</span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    ArrayList&lt;ArrayList&lt;Integer&gt;&gt; result = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    ArrayList&lt;Integer&gt; path = <span class="keyword">new</span> ArrayList&lt;&gt;();</span><br><span class="line">    <span class="keyword">public</span> ArrayList&lt;ArrayList&lt;Integer&gt;&gt; FindPath(TreeNode root,<span class="keyword">int</span> target) &#123;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>) <span class="keyword">return</span> result;</span><br><span class="line">        path.add(root.val);</span><br><span class="line">        target -= root.val;</span><br><span class="line">        <span class="keyword">if</span> (target == <span class="number">0</span> &amp;&amp; root.left == <span class="keyword">null</span> &amp;&amp; root.right == <span class="keyword">null</span>) &#123;</span><br><span class="line">            result.add(<span class="keyword">new</span> ArrayList&lt;&gt;(path));</span><br><span class="line">        &#125;</span><br><span class="line">        FindPath(root.left, target);</span><br><span class="line">        FindPath(root.right, target);</span><br><span class="line">        path.remove(path.size() - <span class="number">1</span>);</span><br><span class="line">        <span class="keyword">return</span> result;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="6-8-对称的二叉树"><a href="#6-8-对称的二叉树" class="headerlink" title="6.8 对称的二叉树"></a>6.8 对称的二叉树</h3><blockquote>
<p>题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。</p>
</blockquote>
<p>思路：下图即为一个对称二叉树。我们需要判断根节点的左右节点是否相等，以及左节点的左子节点与右节点的右子节点是否相等，左节点的右子节点与右节点的左子节点是否相等。</p>
<p><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/332.jpg" alt=""></p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">public class TreeNode &#123;</span></span><br><span class="line"><span class="comment">    int val = 0;</span></span><br><span class="line"><span class="comment">    TreeNode left = null;</span></span><br><span class="line"><span class="comment">    TreeNode right = null;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    public TreeNode(int val) &#123;</span></span><br><span class="line"><span class="comment">        this.val = val;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">    &#125;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">boolean</span> <span class="title">isSymmetrical</span><span class="params">(TreeNode pRoot)</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (pRoot == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="keyword">return</span> isEquals(pRoot.left, pRoot.right);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">boolean</span> <span class="title">isEquals</span><span class="params">(TreeNode node1, TreeNode node2)</span> </span>&#123;</span><br><span class="line">        <span class="comment">// 如果两个节点同时为空，返回true</span></span><br><span class="line">        <span class="keyword">if</span> (node1 == <span class="keyword">null</span> &amp;&amp; node2 == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        <span class="comment">// 如果两个节点不同时为空，返回false</span></span><br><span class="line">        <span class="keyword">if</span> (node1 == <span class="keyword">null</span> || node2 == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">        <span class="comment">// 判断节点值是否相等</span></span><br><span class="line">        <span class="keyword">if</span> (node1.val == node2.val) &#123;</span><br><span class="line">            <span class="keyword">return</span> isEquals(node1.left, node2.right) &amp;&amp; isEquals(node1.right, node2.left);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">Shen Shilei</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://blog.shenshilei.site/post/e1b0/">https://blog.shenshilei.site/post/e1b0/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://blog.shenshilei.site" target="_blank">ShenShilei's Blog</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">算法</a></div><div class="post_share"><div class="social-share" data-image="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/317.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button"><i class="fas fa-qrcode"></i> 打赏<div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/WeChanSQ.png" target="_blank"><img class="post-qr-code-img" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/WeChanSQ.png" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/AliPayQR.png" target="_blank"><img class="post-qr-code-img" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/AliPayQR.png" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/post/e238/"><img class="prev-cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/317.jpg" onerror="onerror=null;src='/img/404.jpg'"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">剑指Offer-二维数组的查找</div></div></a></div><div class="next-post pull-right"><a href="/post/94c0/"><img class="next-cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/317.jpg" onerror="onerror=null;src='/img/404.jpg'"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">剑指Offer-快速幂</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span> 相关推荐</span></div><div class="relatedPosts-list"><div><a href="/post/9ab8/" title="LeetCode-两数之和"><img class="cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/357.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-05-04</div><div class="title">LeetCode-两数之和</div></div></a></div><div><a href="/post/7a42/" title="算法汇总整理"><img class="cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/350.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-09-06</div><div class="title">算法汇总整理</div></div></a></div><div><a href="/post/b550/" title="LeetCode-24点游戏(每日一题)"><img class="cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/357.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-08-22</div><div class="title">LeetCode-24点游戏(每日一题)</div></div></a></div><div><a href="/post/71ac/" title="LeetCode-N皇后(每日一题)"><img class="cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/357.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-09-03</div><div class="title">LeetCode-N皇后(每日一题)</div></div></a></div><div><a href="/post/651a/" title="LeetCode-二叉树的所有路径(每日一题)"><img class="cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/357.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-09-04</div><div class="title">LeetCode-二叉树的所有路径(每日一题)</div></div></a></div><div><a href="/post/3b3c/" title="LeetCode-二叉树的最小深度(每日一题)"><img class="cover" src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/357.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-08-21</div><div class="title">LeetCode-二叉树的最小深度(每日一题)</div></div></a></div></div></div><hr/><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="fas fa-comments fa-fw"></i><span> 评论</span></div></div><div class="comment-wrap"><div><div class="vcomment" id="vcomment"></div></div></div></div></div><div class="aside_content" id="aside_content"><div class="card-widget card-info"><div class="card-content"><div class="card-info-avatar is-center"><img class="avatar-img" src="https://cdn.jsdelivr.net/gh/shenshilei1022/cdn@1.6/img/custom/avatar.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/><div class="author-info__name">Shen Shilei</div><div class="author-info__description"></div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">92</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">标签</div><div class="length-num">60</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">分类</div><div class="length-num">38</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/shenshilei1022"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/shenshilei1022" target="_blank" title="Github"><i class="iconfont icon-github1"></i></a><a class="social-icon" href="mailto:1774822536@qq.com" target="_blank" title="Email"><i class="iconfont icon-youxiang"></i></a><a class="social-icon" href="https://gitee.com/shenshilei1022" target="_blank" title="Gitee"><i class="iconfont icon-github2"></i></a><a class="social-icon" href="https://music.163.com/#/user/home?id=77600006" target="_blank" title="Netease Music"><i class="iconfont icon-wangyiyunyinle"></i></a><a class="social-icon" href="https://space.bilibili.com/15250718" target="_blank" title="Bilibili"><i class="iconfont icon-bilibili1"></i></a></div></div></div><div class="card-widget card-announcement"><div class="card-content"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">活在当下</div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="card-content"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#1-%E4%B8%BA%E4%BB%80%E4%B9%88%E8%A6%81%E4%BD%BF%E7%94%A8%E6%A0%91%EF%BC%9F"><span class="toc-text">1. 为什么要使用树？</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#2-%E6%A0%91"><span class="toc-text">2. 树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#3-%E6%A0%91%E7%9A%84%E5%B8%B8%E7%94%A8%E5%90%8D%E8%AF%8D"><span class="toc-text">3. 树的常用名词</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#4-%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">4. 二叉树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#5-%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86"><span class="toc-text">5. 树的遍历</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#6-%E5%87%A0%E4%B8%AA%E5%85%B3%E4%BA%8E%E6%A0%91%E7%9A%84%E9%A2%98%E7%9B%AE"><span class="toc-text">6. 几个关于树的题目</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#6-1-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E6%B7%B1%E5%BA%A6"><span class="toc-text">6.1 二叉树的深度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-2-%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%95%9C%E5%83%8F"><span class="toc-text">6.2 二叉树的镜像</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-3-%E9%87%8D%E5%BB%BA%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">6.3 重建二叉树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-4-%E5%BA%8F%E5%88%97%E5%8C%96%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">6.4 序列化二叉树</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-5-%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97"><span class="toc-text">6.5 二叉搜索树的后序遍历序列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-6-%E6%A0%91%E7%9A%84%E5%AD%90%E7%BB%93%E6%9E%84"><span class="toc-text">6.6 树的子结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-7-%E4%BA%8C%E5%8F%89%E6%A0%91%E4%B8%AD%E5%92%8C%E4%B8%BA%E6%9F%90%E4%B8%80%E5%80%BC%E7%9A%84%E8%B7%AF%E5%BE%84"><span class="toc-text">6.7 二叉树中和为某一值的路径</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-8-%E5%AF%B9%E7%A7%B0%E7%9A%84%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-text">6.8 对称的二叉树</span></a></li></ol></li></ol></div></div></div><div class="card-widget card-recent-post"><div class="card-content"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/post/ceb5/" title="在Deepin上安装Eclipse"><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/20210911113215.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="在Deepin上安装Eclipse"/></a><div class="content"><a class="title" href="/post/ceb5/" title="在Deepin上安装Eclipse">在Deepin上安装Eclipse</a><time datetime="2021-09-11T02:46:06.000Z" title="发表于 2021-09-11 10:46:06">2021-09-11</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/post/6b0/" title="使用VMware创建CentOS7.6虚拟机"><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/centos-motif.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="使用VMware创建CentOS7.6虚拟机"/></a><div class="content"><a class="title" href="/post/6b0/" title="使用VMware创建CentOS7.6虚拟机">使用VMware创建CentOS7.6虚拟机</a><time datetime="2021-03-07T14:56:59.000Z" title="发表于 2021-03-07 22:56:59">2021-03-07</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/post/1ea5/" title="前端练习-九宫格"><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/353.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="前端练习-九宫格"/></a><div class="content"><a class="title" href="/post/1ea5/" title="前端练习-九宫格">前端练习-九宫格</a><time datetime="2020-09-14T09:06:40.000Z" title="发表于 2020-09-14 17:06:40">2020-09-14</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/post/7240/" title="LeetCode-组合(每日一题)"><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/357.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LeetCode-组合(每日一题)"/></a><div class="content"><a class="title" href="/post/7240/" title="LeetCode-组合(每日一题)">LeetCode-组合(每日一题)</a><time datetime="2020-09-08T07:13:45.000Z" title="发表于 2020-09-08 15:13:45">2020-09-08</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/post/aeeb/" title="LeetCode-前K个高频元素(每日一题)"><img src="https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/357.jpg" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="LeetCode-前K个高频元素(每日一题)"/></a><div class="content"><a class="title" href="/post/aeeb/" title="LeetCode-前K个高频元素(每日一题)">LeetCode-前K个高频元素(每日一题)</a><time datetime="2020-09-07T08:46:04.000Z" title="发表于 2020-09-07 16:46:04">2020-09-07</time></div></div></div></div></div></div></div></main><footer id="footer" style="background-image: url(https://gitee.com/shenshilei1022/hugo_image_resource/raw/master/imgs/317.jpg)"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2021 By Shen Shilei</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">回首向来萧瑟处，归去，也无风雨也无晴。</div><div class="icp"><a><img class="icp-icon" src="/img/icp.png" alt="ICP"/><span>陕ICP备2020013027号</span></a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="fas fa-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div id="local-search"><div class="search-dialog"><div class="search-dialog__title" id="local-search-title">本地搜索</div><div id="local-input-panel"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div></div><hr/><div id="local-search-results"><div id="local-hits"></div><div id="local-stats"><div class="local-search-stats__hr" id="hr"><span>由</span> <a target="_blank" rel="noopener" href="https://github.com/wzpan/hexo-generator-search" style="color:#49B1F5;">hexo-generator-search</a>
 <span>提供支持</span></div></div></div><span class="search-close-button"><i class="fas fa-times"></i></span></div><div id="search-mask"></div></div><div><script src="https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js"></script><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js"></script><script src="https://cdn.jsdelivr.net/npm/node-snackbar/dist/snackbar.min.js"></script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>function loadValine () {
  function initValine () {
    let initData = {
      el: '#vcomment',
      appId: 'A2SjWuspv5TQF8rzabRx8Y1d-MdYXbMMI',
      appKey: 'SYbn4zrNF0biLCBhwQ0956wm',
      placeholder: '留下你的足迹...(昵称中填写QQ号可使用QQ头像和QQ邮箱)',
      avatar: 'monsterid',
      meta: 'nick,mail,link'.split(','),
      pageSize: '10',
      lang: 'zh-CN',
      recordIP: false,
      serverURLs: '',
      emojiCDN: 'https://cdn.jsdelivr.net/gh/shenshilei1022/emotion@1.0/',
      emojiMaps: {"1":"aru/1.png","2":"aru/2.png","3":"aru/3.png","4":"aru/4.png","5":"aru/5.png","6":"aru/6.png","7":"aru/7.png","8":"aru/8.png","9":"aru/9.png","10":"aru/10.png","11":"aru/11.png","12":"aru/12.png","13":"aru/13.png","14":"aru/14.png","15":"aru/15.png","16":"aru/16.png","17":"aru/17.png","18":"aru/18.png","19":"aru/19.png","20":"aru/20.png","21":"aru/21.png","22":"aru/22.png","23":"aru/23.png","24":"aru/24.png","25":"aru/25.png","26":"aru/26.png","27":"aru/27.png","28":"aru/28.png","29":"aru/29.png","30":"aru/30.png","31":"aru/31.png","32":"aru/32.png","33":"aru/33.png","34":"aru/34.png","35":"aru/35.png","36":"aru/36.png","37":"aru/37.png","38":"aru/38.png","39":"猥琐萌/1.jpg","40":"猥琐萌/2.jpg","41":"猥琐萌/3.jpg","42":"猥琐萌/4.jpg","43":"猥琐萌/5.jpg","44":"猥琐萌/6.jpg","45":"猥琐萌/7.jpg","46":"猥琐萌/8.jpg","47":"猥琐萌/9.jpg","48":"猥琐萌/10.jpg","49":"猥琐萌/11.jpg","50":"猥琐萌/12.jpg","51":"猥琐萌/13.jpg","52":"猥琐萌/14.jpg","53":"猥琐萌/15.jpg","54":"猥琐萌/16.jpg","55":"猥琐萌/17.jpg","56":"猥琐萌/18.jpg","57":"猥琐萌/19.jpg","58":"猥琐萌/20.jpg","59":"猥琐萌/21.jpg","60":"猥琐萌/22.jpg","61":"猥琐萌/23.jpg","62":"猥琐萌/24.jpg","63":"猥琐萌/25.jpg","64":"猥琐萌/26.jpg","65":"猥琐萌/27.jpg","66":"猥琐萌/28.jpg","67":"猥琐萌/29.jpg","68":"猥琐萌/30.jpg","69":"猥琐萌/31.jpg","70":"猥琐萌/32.jpg","71":"猥琐萌/33.jpg","72":"猥琐萌/34.jpg","73":"猥琐萌/35.jpg","74":"猥琐萌/36.jpg","75":"猥琐萌/37.jpg","76":"猥琐萌/38.jpg","77":"猥琐萌/39.jpg","78":"猥琐萌/40.jpg","79":"猥琐萌/41.jpg","80":"猥琐萌/42.jpg","81":"猥琐萌/43.jpg","82":"猥琐萌/44.jpg","83":"猥琐萌/45.jpg","84":"猥琐萌/46.jpg","85":"猥琐萌/47.jpg","86":"猥琐萌/48.jpg","87":"猥琐萌/49.jpg","88":"猥琐萌/50.jpg","89":"猥琐萌/51.jpg","90":"猥琐萌/52.jpg","91":"猥琐萌/53.jpg","92":"猥琐萌/54.jpg","93":"猥琐萌/55.jpg","94":"猥琐萌/56.jpg","95":"猥琐萌/57.jpg","96":"猥琐萌/58.jpg","97":"猥琐萌/59.jpg","98":"猥琐萌/60.jpg","djxbz":"copy/djxbz.jpg","gan":"copy/gan.jpg","hp":"copy/hp.jpg","huaiyi":"copy/huaiyi.jpg","imgcao":"copy/imgcao.jpg","imghua":"copy/imghua.jpg","imgri":"copy/imgri.jpg","mudenggoudai":"copy/mudenggoudai.jpg","pc":"copy/pc.jpg","tlspg":"copy/tlspg.jpg","tql":"copy/tql.jpg","wuyu":"copy/wuyu.jpg","zzxbz":"copy/zzxbz.jpg","icon_huaji":"copy/icon_huaji.png","仙女下凡":"copy/仙女下凡.webp","听歌":"copy/听歌.webp","嫌弃":"copy/嫌弃.webp","害羞":"bilibili/tv_害羞.png","彩虹滑稽":"copy/彩虹滑稽.webp","快走":"copy/快走.webp","扯脸":"copy/扯脸.webp","摸脸":"copy/摸脸.webp","流汗":"bilibili/tv_流汗.png","滑滑板":"copy/滑滑板.webp","点赞":"bilibili/tv_点赞.png","转圈圈":"copy/转圈圈.webp","光头小人1":"copy/光头小人_(1).gif","光头小人19":"copy/光头小人_(19).gif","光头小人20":"copy/光头小人_(20).gif","光头小人21":"copy/光头小人_(21).gif","光头小人22":"copy/光头小人_(22).gif","光头小人23":"copy/光头小人_(23).gif","光头小人24":"copy/光头小人_(24).gif","光头小人25":"copy/光头小人_(25).gif","光头小人26":"copy/光头小人_(26).gif","光头小人27":"copy/光头小人_(27).gif","光头小人28":"copy/光头小人_(28).gif","光头小人29":"copy/光头小人_(29).gif","光头小人30":"copy/光头小人_(30).gif","光头小人31":"copy/光头小人_(31).gif","光头小人32":"copy/光头小人_(32).gif","光头小人33":"copy/光头小人_(33).gif","光头小人34":"copy/光头小人_(34).gif","光头小人35":"copy/光头小人_(35).gif","光头小人36":"copy/光头小人_(36).gif","光头小人37":"copy/光头小人_(37).gif","光波":"copy/光波.gif","厕所1":"copy/厕所_(1).gif","厕所2":"copy/厕所_(2).gif","厕所3":"copy/厕所_(3).gif","咸鱼":"copy/咸鱼.gif","奏乐1":"copy/奏乐_(1).gif","奏乐10":"copy/奏乐_(10).gif","奏乐2":"copy/奏乐_(2).gif","奏乐4":"copy/奏乐_(4).gif","奏乐5":"copy/奏乐_(5).gif","奏乐6":"copy/奏乐_(6).gif","奏乐7":"copy/奏乐_(7).gif","奏乐8":"copy/奏乐_(8).gif","奏乐9":"copy/奏乐_(9).gif","奔跑狗5":"copy/奔跑狗 (5).gif","奔跑狗1":"copy/奔跑狗_(1).gif","奔跑狗2":"copy/奔跑狗_(2).gif","奔跑狗3":"copy/奔跑狗_(3).gif","奔跑狗4":"copy/奔跑狗_(4).gif","害怕滑稽":"copy/害怕滑稽.gif","小人儿10":"copy/小人儿_(10).gif","小兔吃东西12":"copy/小兔吃东西_(12).gif","小兔吃东西13":"copy/小兔吃东西_(13).gif","小兔吃东西14":"copy/小兔吃东西_(14).gif","小兔吃东西18":"copy/小兔吃东西_(18).gif","小兔吃东西19":"copy/小兔吃东西_(19).gif","小兔吃东西20":"copy/小兔吃东西_(20).gif","小兔吃东西21":"copy/小兔吃东西_(21).gif","小兔吃东西22":"copy/小兔吃东西_(22).gif","小疯子2":"copy/小疯子_(2).gif","小疯子3":"copy/小疯子_(3).gif","小疯子4":"copy/小疯子_(4).gif","小疯子5":"copy/小疯子_(5).gif","小疯子6":"copy/小疯子_(6).gif","小疯子7":"copy/小疯子_(7).gif","小疯子8":"copy/小疯子_(8).gif","扇子狗":"copy/扇子狗.gif","抓1":"copy/抓_(1).gif","抓2":"copy/抓_(2).gif","掐脖子":"copy/掐脖子.gif","滑稽1":"copy/滑稽_(1).gif","滑稽2":"copy/滑稽_(2).gif","滑稽3":"copy/滑稽_(3).gif","滑稽4":"copy/滑稽_(4).gif","跪坐1":"copy/跪坐_(1).gif","跪坐2":"copy/跪坐_(2).gif","鹦鹉小恐龙1":"copy/鹦鹉小恐龙_(1).gif","鹦鹉小恐龙2":"copy/鹦鹉小恐龙_(2).gif","doge":"bilibili/tv_doge.png","亲亲":"bilibili/tv_亲亲.png","偷笑":"bilibili/tv_偷笑.png","再见":"bilibili/tv_再见.png","冷漠":"bilibili/tv_冷漠.png","发怒":"bilibili/tv_发怒.png","发财":"bilibili/tv_发财.png","可爱":"bilibili/tv_可爱.png","吐血":"bilibili/tv_吐血.png","呆":"bilibili/tv_呆.png","呕吐":"bilibili/tv_呕吐.png","困":"bilibili/tv_困.png","坏笑":"bilibili/tv_坏笑.png","大佬":"bilibili/tv_大佬.png","大哭":"bilibili/tv_大哭.png","委屈":"bilibili/tv_委屈.png","尴尬":"bilibili/tv_尴尬.png","微笑":"bilibili/tv_微笑.png","思考":"bilibili/tv_思考.png","惊吓":"bilibili/tv_惊吓.png","打脸":"bilibili/tv_打脸.png","抓狂":"bilibili/tv_抓狂.png","抠鼻":"bilibili/tv_抠鼻.png","斜眼笑":"bilibili/tv_斜眼笑.png","无奈":"bilibili/tv_无奈.png","晕":"bilibili/tv_晕.png","流泪":"bilibili/tv_流泪.png","流鼻血":"bilibili/tv_流鼻血.png","生气":"bilibili/tv_生气.png","生病":"bilibili/tv_生病.png","疑问":"bilibili/tv_疑问.png","白眼":"bilibili/tv_白眼.png","皱眉":"bilibili/tv_皱眉.png","目瞪口呆":"bilibili/tv_目瞪口呆.png","睡着":"bilibili/tv_睡着.png","笑哭":"bilibili/tv_笑哭.png","腼腆":"bilibili/tv_腼腆.png","色":"bilibili/tv_色.png","调侃":"bilibili/tv_调侃.png","调皮":"bilibili/tv_调皮.png","鄙视":"bilibili/tv_鄙视.png","闭嘴":"bilibili/tv_闭嘴.png","难过":"bilibili/tv_难过.png","馋":"bilibili/tv_馋.png","鬼脸":"bilibili/tv_鬼脸.png","黑人问号":"bilibili/tv_黑人问号.png","鼓掌":"bilibili/tv_鼓掌.png"},
      enableQQ: true,
      path: window.location.pathname,
    }

    if (true) { 
      initData.requiredFields= ('nick,mail'.split(','))
    }
    
    if (false) {
      const otherData = false
      initData = Object.assign({}, initData, otherData)
    }
    
    const valine = new Valine(initData)
  }

  if (typeof Valine === 'function') initValine() 
  else $.getScript('https://cdn.jsdelivr.net/npm/valine/dist/Valine.min.js', initValine)
}

if ('Valine' === 'Valine' || !false) {
  if (false) btf.loadComment(document.querySelector('#vcomment'),loadValine)
  else setTimeout(() => loadValine(), 0)
} else {
  function loadOtherComment () {
    loadValine()
  }
}</script><script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div><div class="aplayer no-destroy" data-id="4960099490" data-server="netease" data-type="playlist" data-fixed="true" data-mini="true" data-listFolded="false" data-order="random" data-preload="none" data-autoplay="false" muted></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.css"><script src="https://cdn.jsdelivr.net/npm/aplayer/dist/APlayer.min.js"></script><script src="https://cdn.jsdelivr.net/gh/metowolf/MetingJS@1.2/dist/Meting.min.js"></script><script src="https://cdn.jsdelivr.net/npm/pjax/pjax.min.js"></script><script>let pjaxSelectors = [
  'title',
  '#config_change',
  '#body-wrap',
  '#rightside-config-hide',
  '#rightside-config-show',
  '.js-pjax'
]

if (false) {
  pjaxSelectors.unshift('meta[property="og:image"]', 'meta[property="og:title"]', 'meta[property="og:url"]')
}

var pjax = new Pjax({
  elements: 'a:not([target="_blank"]):not([href="/post/a7b7/"]):not([href="/artitalk/"]):not([href="/post/6a69/"])',
  selectors: pjaxSelectors,
  cacheBust: false,
  analytics: false,
  scrollRestoration: false
})

document.addEventListener('pjax:complete', function () {
  window.refreshFn()

  $('script[data-pjax]').each(function () {
    $(this).parent().append($(this).remove())
  })

  GLOBAL_CONFIG.islazyload && window.lazyLoadInstance.update()

  typeof chatBtnFn === 'function' && chatBtnFn()
  typeof panguInit === 'function' && panguInit()

  if (typeof gtag === 'function') {
    gtag('config', '', {'page_path': window.location.pathname});
  }

  typeof loadMeting === 'function' && document.getElementsByClassName('aplayer').length && loadMeting()

  // Analytics
  if (false) {
    MtaH5.pgv()
  }

  // prismjs
  typeof Prism === 'object' && Prism.highlightAll()

  typeof preloader === 'object' && preloader.endLoading()
})


document.addEventListener('pjax:send', function () {
  typeof preloader === 'object' && preloader.initLoading()
  
  if (window.aplayers) {
    for (let i = 0; i < window.aplayers.length; i++) {
      if (!window.aplayers[i].options.fixed) {
        window.aplayers[i].destroy()
      }
    }
  }

  typeof typed === 'object' && typed.destroy()

  $(window).off('scroll')

  //reset readmode
  $('body').hasClass('read-mode') && $('body').removeClass('read-mode')

})</script></div></body></html>